July 17, 2023
N개의 정수로 구성된 비어 있지 않은 배열 A가 주어집니다.
피크는 이웃 요소보다 큰 배열 요소입니다. 더 정확하게는 0 < P < N - 1, A[P - 1] < A[P] > A[P + 1]이 되는 인덱스 P입니다.
예를 들어, 다음 배열 A:
A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2에는 정확히 4개의 피크가 있습니다: 요소 1, 3, 5, 10.
아래 그림과 같이 상대적인 높이가 배열 A로 표시되는 여러 산으로 여행을 떠난다고 가정해 보겠습니다. 얼마나 많은 깃발을 가져갈지 선택해야 합니다. 목표는 특정 규칙에 따라 봉우리에 최대 깃발 수를 설정하는 것입니다.
깃발은 봉우리에만 설정할 수 있습니다. 또한 K개의 깃발을 사용하는 경우 두 깃발 사이의 거리는 K보다 크거나 같아야 합니다. 인덱스 P와 Q 사이의 거리는 절대값인 |P - Q|입니다.
예를 들어, 위의 배열 A로 표시된 산맥이 있고 N이 12라고 가정해 보겠습니다:
함수를 작성합니다:
function solution(A);비어 있지 않은 정수 배열 A가 주어지면 배열의 피크에 설정할 수 있는 최대 플래그 수를 반환하는 함수입니다.
예를 들어, 다음 배열 A를 살펴보겠습니다:
A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2이면 위에서 설명한 대로 함수는 3을 반환해야 합니다.
다음 가정에 대한 효율적인 알고리즘을 작성합니다:
이 문제 아직 잘 이해가 가지 않는다. … 조금 더 파악해봐야겠어요..
function solution(A) {
const peaks = [];
for (let i = 1; i < A.length - 1; i++){
if (A[i] > A[i-1] && A[i] > A[i+1]) {
peaks.push(i);
}
}
// 1. 주어진 배열에서 피크를 찾아 'peaks' 배열에 저장합니다.
if (peaks.length === 0) return 0;
// 2. 만약 피크가 없다면, 플래그를 위치시킬 수 없으므로 0을 반환합니다.
let result = 1;
let possibleResult = Math.min(peaks.length, Math.floor(Math.sqrt(A.length - 1)) + 1);
// 3. 'possibleResult'는 가능한 플래그의 최대 수를 의미하며, 이는 피크의 수와 배열 길이의 제곱근 중 작은 값입니다.
for (let i = possibleResult; i >= 1; i--){
let flags = 1;
let pos = peaks[0];
for (let j = 1; j < peaks.length; j++){
if (peaks[j] >= pos+i){
pos = peaks[j];
flags++;
}
if (flags === i) {
break;
}
}
result = Math.max(result, flags);
}
// 4. possibleResult부터 1까지 모든 값을 확인하면서, 각각의 값에 대해 최대한 많은 플래그를 배치해 봅니다.
// 만약 i개의 플래그를 배치할 수 있다면, 그것이 최대 값이 됩니다.
return result;
// 5. 최종적으로 가장 많은 플래그를 배치할 수 있는 값을 반환합니다.
}